package com.yww.leetcode.binarysearch;

/**
 * @author yww
 * @description 34. 在排序数组中查找元素的第一个和最后一个位置
 * @since 2024/1/29 15:18
 */
public class SearchRange34 {
    // 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。
    // 请你找出给定目标值在数组中的开始位置和结束位置。
    // 如果数组中不存在目标值 target，返回 [-1, -1]。
    public int[] searchRange(int[] nums, int target) {
        int leftRes = left(nums, target);

        if (leftRes == -1) {
            return new int[]{-1, -1};
        } else {
            return new int[]{leftRes, right(nums, target)};
        }
    }

    public static int left(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < nums[m]) {
                j = m - 1;
            } else if (nums[m] < target) {
                i = m + 1;
            } else {
                j = m - 1;
                candidate = m;
            }

        }
        return candidate;
    }

    public static int right(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < nums[m]) {
                j = m - 1;
            } else if (nums[m] < target) {
                i = m + 1;
            } else {
                i = m + 1;
                candidate = m;
            }

        }
        return candidate;
    }
}
